{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align: right\"><i>Peter Norvig<br>April 2015</i></div>\n",
    "\n",
    "# When is Cheryl's Birthday?\n",
    "\n",
    "\n",
    "**[This logic puzzle](https://en.wikipedia.org/wiki/Cheryl%27s_Birthday)** has been making the rounds:\n",
    "\n",
    "1. Albert and Bernard became friends with Cheryl, and want to know when her birthday is. Cheryl gives them a list of 10 possible dates:\n",
    "   - May 15,     May 16,     May 19\n",
    "   - June 17,    June 18\n",
    "   - July 14,    July 16\n",
    "   - August 14,  August 15,  August 17\n",
    "3. **Cheryl** then privately tells Albert the month and Bernard the day of her birthday.\n",
    "4. **Albert**: \"I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\n",
    "5. **Bernard**: \"At first I didn't know when Cheryl's birthday is, but I know now.\"\n",
    "6. **Albert**: \"Then I also know when Cheryl's birthday is.\"\n",
    "7. So when is Cheryl's birthday?\n",
    "\n",
    "This puzzle is designed for a paper-and-pencil solution, but I'm going to solve it with code; code is more flexible and can be used to solve other similar puzzles. Let's work through the puzzle line by line.\n",
    "\n",
    "## 1. Cheryl gives Albert and Bernard a list of 10 possible dates:\n",
    "\n",
    "The result of this is that Albert and Bernard each know the birthday is one of ten dates, but they don't know which date. We'll call a set of possible dates a **belief state**. As additional statements are made, each character's belief state will change. When someone has a belief state with just one possibility, we say they **know** the true value.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "BeliefState = set # A set of possible values\n",
    "\n",
    "DATES = BeliefState({'May 15', 'May 16', 'May 19', 'June 17', 'June 18', \n",
    "                     'July 14', 'July 16', 'August 14', 'August 15', 'August 17'})\n",
    "\n",
    "def know(beliefs: BeliefState) -> bool:\n",
    "    \"\"\"A person `knows` the correct value if their belief state has only one possibility.\"\"\"\n",
    "    return len(beliefs) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll define accessor functions for the month and day of a date:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def month(date: str) -> str: return date.split()[0]\n",
    "def day(date: str)   -> str: return date.split()[1]\n",
    "\n",
    "assert month('May 15') == 'May'\n",
    "assert   day('May 15') == '15'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Cheryl then privately tells Albert the month and Bernard the day of her birthday.\n",
    "\n",
    "We can define the idea of Cheryl having **told** someone a component of her birthdate, thus updating their belief state:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def told(part: str) -> BeliefState:\n",
    "    \"\"\"Cheryl told a part of her birthdate to someone; return a belief state of possible dates.\"\"\"\n",
    "    return {date for date in DATES if part in date}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(*Note*: I dislike it that the function `told` uses the global constant `DATES`. But I can live with it.)\n",
    "\n",
    "Let's consider `'May 15'` as a possible birthdate. Cheryl tells Albert `'May'` and Bernard `'15'`, so they would have  these belief states, and they would not *know* the birthday:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert told('May') == {'May 15', 'May 16', 'May 19'} # Albert's belief state\n",
    "assert told('15')  == {'August 15', 'May 15'}        # Bernard's belief state\n",
    "assert not know(told('May'))                         # Albert does not know\n",
    "assert not know(told('15'))                          # Bernard does not know"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now consider  `'June 18'`; in this case, Bernard would *know*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert told('June') == {'June 17', 'June 18'}  # Albert's belief state\n",
    "assert told('18') == {'June 18'}               # Bernard's belief state\n",
    "assert not know(told('June'))                  # Albert does not know\n",
    "assert know(told('18'))                        # Bernard DOES know"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overall Strategy\n",
    "\n",
    "The puzzle is tricky because we're dealing with two types of uncertainty:\n",
    "\n",
    "1. Albert and Bernard are initially uncertain about the birthdate. *(Cheryl knows something they don't know.)*\n",
    "2. We (the puzzle solvers) don't know what Albert and Bernard were told by Cheryl. *(They know something we don't know.)*\n",
    "\n",
    "If Cheryl tells Albert that the month is \"May\",  his belief state becomes {May 15, May 16, May 19}.  But we the puzzle solvers don't know what month he was told. To deal with this we will consider each of the ten dates one at a time and reason as follows: \n",
    "- For each date, we know what Albert and Bernard were told; we have eliminated the second type of uncertainty. \n",
    "- We can thus figure out if Albert and Bernard's statements are true (given this date). \n",
    "- There should be only one date out of the ten that makes all the statements true; that's Cheryl's birthday.\n",
    "\n",
    "Here is the main function, `cheryls_birthday`, which computes the subset of possible dates that satisfy Albert and Bernard's statements.  We will implement a **statement** as a boolean function that takes a single date as input and returns true if the statement would be true under the condition that the given date is Cheryl's actual birthday. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cheryls_birthday() -> BeliefState:\n",
    "    \"\"\"Return a subset of the global `DATES` for which all three statements are true.\"\"\"\n",
    "    return satisfy(DATES, albert1, bernard1, albert2)\n",
    "\n",
    "## TODO: Implement statements albert1, bernard1, albert2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `satisfy` takes a belief state and some statements and returns the subset that satisfies all the statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def satisfy(beliefs: BeliefState, *statements) -> BeliefState:\n",
    "    \"\"\"Return the subset of values in `beliefs` that satisfy all the statements.\"\"\"\n",
    "    return {value for value in beliefs if all(statement(value) for statement in statements)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Albert: I don't know when Cheryl's birthday is, and I know that Bernard does not know."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first rephrase this statement to use the concepts we have defined:\n",
    "\n",
    "**Albert**: *After Cheryl **told** me the **month** of her birthdate, my **belief state** is a set of dates such that I didn't **know** her birthday.  And I know that Bernard does not know. How do I know that? I can see that there are no possible dates that Bernard would **know** Cheryl's birthday if he was **told** the **day** of that date.*\n",
    "\n",
    "That I can translate directly into code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def albert1(date: str) -> bool:\n",
    "    \"\"\"Albert: I don't know when Cheryl's birthday is, and I know that Bernard does not know.\"\"\"\n",
    "    dates = told(month(date))\n",
    "    return not know(dates) and not satisfy(dates, lambda date: know(told(day(date))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We haven't solved the puzzle yet, but let's take a peek and see which dates satisfy Albert's first statement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 14', 'August 15', 'August 17', 'July 14', 'July 16'}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(DATES, albert1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Bernard: At first I didn't know when Cheryl's birthday is, but I know now.\n",
    "\n",
    "Again, a paraphrase:\n",
    "\n",
    "**Bernard:** *At first Cheryl **told** me the **day**, and I didn't **know**.  After I heard Albert's **statement**, I updated my **belief state**, and now I **know**.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bernard1(date: str) -> bool:\n",
    "    \"Bernard: At first I don't know when Cheryl's birthday is, but I know now.\"\n",
    "    at_first = told(day(date))\n",
    "    now      = satisfy(at_first, albert1)\n",
    "    return not know(at_first) and know(now)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see which dates satisfy the two statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'August 15', 'August 17', 'July 16'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "satisfy(DATES, albert1, bernard1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wait a minute–I thought that Bernard **knew**?! Why are there **three** possible dates? \n",
    "\n",
    "According to the puzzle, Bernard does indeed know; it is just that we, the puzzle solvers, don't know yet.  That's because Bernard was told something we don't know: the day. If Bernard was told `'15'` then he would know `'August 15'`; if he was told `'17'` he would know `'August 17'`, and if he was told `'16'` he would know `'July 16'`. We'll need more information (coming in statement `albert2`) before *we* know.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Albert: Then I also know when Cheryl's birthday is.\n",
    "\n",
    "A paraphrase:\n",
    "\n",
    "**Albert**: *After being **told** the **month** and hearing Bernard's **statement**, I now **know** Cheryl's birthday.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def albert2(date: str) -> bool:\n",
    "    \"Albert: Then I also know when Cheryl's birthday is.\" \n",
    "    now = satisfy(told(month(date)), bernard1)\n",
    "    return know(now)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. So when is Cheryl's birthday?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'July 16'}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cheryls_birthday()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Success!** We have deduced that Cheryl's birthday is **July 16**. We know Cheryl's birthday:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert know(cheryls_birthday())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
